package top.hkyzf.study.leetcode.string;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * description:
 *
 * @author zhufeng
 * @version 1.0
 * @date 2024-3-17 11:29
 */
public class 成为_K_特殊字符串需要删除的最少字符数_100255 {
    public int minimumDeletions(String word, int k) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < word.length(); i++) {
            map.put(word.charAt(i), map.getOrDefault(word.charAt(i), 0) + 1);
        }
        List<Integer> values = map.values().stream().sorted().collect(Collectors.toList());
        int rtn = Integer.MAX_VALUE;
        for (int i = 0; i < values.size(); i++) {
            int start = values.get(i);
            int end = start + k;
            int min = findMin(values, start, end);
            rtn = Math.min(rtn, min);
        }
        return rtn;
    }

    private int findMin(List<Integer> integers, int start, int end) {
        // 剩余最大数字减去最小数字 小于等于 k
        int min = 0;
        for (Integer integer : integers) {
            if (integer < start) {
                min += integer;
            } else if (integer > end) {
                min += integer - end;
            }
        }
        return min;
    }

    @Test
    public void testMinimumDeletions () {
        String word = "aabcaba";
        int k = 0;
        System.out.println(minimumDeletions(word, k));
    }
}
